/**
 * @Author: zxc
 * @Date: 2020-11-09 13:19:00
 * @func 正则表达式匹配
 */

//用魔法打败魔法
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  return new RegExp("^" + p + "$").test(s)
}

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  const len = s.length + 1
  const dp = new Array(len)
  let i = 0
  for (; i < len; i++) {
    dp[i] = new Array(len).fill(false)
  }

  dp[0][0] = true // 双空

  for (i = 0; i < p.length; i++) {
    if (p[i] === "*") {
      dp[0][i + 1] = dp[0][i - 1]
    }
  }

  for (let i = 0; i < s.length; i++) {
    for (let j = 0; j < p.length; j++) {
      if (p[j] === s[i] || p[j] === ".") {
        dp[i + 1][j + 1] = dp[i][j]
      }

      if (p[j] === "*") {
        if (p[j - 1] !== s[i] && p[j - 1] !== ".") {
          dp[i + 1][j + 1] = dp[i + 1][j - 1]
        } else {
          dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j - 1] || dp[i + 1][j]
        }
      }
    }
  }

  return dp[s.length][p.length]
}
